module(..., package.seeall)
local lpeg = require "lpeg"

local NUMBER=lpeg.R"09"^1/tonumber
local NAME=lpeg.C((lpeg.R('AZ','az','09','\127\255')+lpeg.P'_')^1)
local PATHPATTERN =lpeg.Ct((lpeg.P"[" * NUMBER * lpeg.P"]" + NAME)*(lpeg.P"[" * NUMBER * lpeg.P"]" + lpeg.P"." * NAME)^0)*-lpeg.P(1)
NUMBER,NAME=nil,nil
function pathinfo(path)
	return PATHPATTERN:match(path)
end
function pathset(t,path,v)
	local segs=PATHPATTERN:match(path)
	if not segs or #segs==0 then error('bad path args '..tostring(path),2) end
	for i=1,#segs-1 do
		local sub=t[segs[i]]
		if sub==nil then sub={};t[segs[i]]=sub end
		t=sub
	end
	local old=t[segs[#segs]]
	t[segs[#segs]]=v
	return old
end

function pathget(t,path)
	local segs=PATHPATTERN:match(path)
	if not segs or #segs==0 then return nil end
	for i=1,#segs do
		if type(t)~='table' then
			return nil
		end
		t=t[segs[i]]
	end
	return t
end

function pathsure(t,path,createval)
	local segs=PATHPATTERN:match(path)
	if not segs or #segs==0 then error('bad path args '..tostring(path),2) end
	for i=1,#segs-1 do
		local sub=t[segs[i]]
		if sub==nil then sub={};t[segs[i]]=sub end
		t=sub
	end
	local old=t[segs[#segs]]
	if old~=nil then return old end
	t[segs[#segs]]=createval
	return createval
end

function count(t)
	if not t then return 0 end
	c=0
	for _ in pairs(t) do
		c=c+1
	end
	return c
end

function array(...) -- abuse to: http://richard.warburton.it
	local newTable,keys,values={},{},{}
	newTable.__each=function(self) -- pairs iterator
		local count=0
		return function() 
			count=count+1
			return keys[count],values[keys[count]]
		end
	end

	setmetatable(newTable,{
		__newindex=function(self,key,value)
			if value==nil then -- Handle item delete
				if nil~=self[key] then
					local count=1
					while keys[count]~=key do count = count + 1 end
					table.remove(keys,count)
				end
			elseif nil==self[key] then
				table.insert(keys,key)
			end
			values[key]=value -- replace/create
		end,
		__index=function(self,key) return values[key] end,
		__len=function(self) return #keys end,
	})
	for x=1,select('#',...),2 do
		local k,v=select(x,...)
		newTable[k]=v
	end
	return newTable
end

--[[
	Binary Search a Table
	Binary Insert into Table (faster than table.insert and table.sort combined)
	v 0.3

	Lua 5.1 compatible
]]--
--[[
	table.binsearch( table, value [, compval [, reversed] ] )
	
	Searches the table through BinarySearch for the given value.
	If the	value is found:
		it returns a table holding all the mathing indices (e.g. { startindice,endindice } )
		endindice may be the same as startindice if only one matching indice was found
	If compval is given:
		then it must be a function that takes one value and returns a second value2,
		to be compared with the input value, e.g.:
		compvalue = function( value ) return value[1] end
	If reversed is set to true:
		then the search assumes that the table is sorted in reverse order (largest value at position 1)
		note when reversed is given compval must be given as well, it can be nil/_ in this case
	Return value:
		on success: a table holding matching indices (e.g. { startindice,endindice } )
		on failure: nil
]]--
do
	-- Avoid heap allocs for performance
	local default_fcompval = function( value ) return value end
	local fcompf = function( a,b ) return a < b end
	local fcompr = function( a,b ) return a > b end
	function binsearch( t,value,fcompval,reversed )
		-- Initialise functions
		local fcompval = fcompval or default_fcompval
		local fcomp = reversed and fcompr or fcompf
		--	Initialise numbers
		local iStart,iEnd,iMid = 1,#t,0
		-- Binary Search
		while iStart <= iEnd do
			-- calculate middle
			iMid = math.floor( (iStart+iEnd)/2 )
			-- get compare value
			local value2 = fcompval( t[iMid] )
			-- get all values that match
			if value == value2 then
				local tfound,num = { iMid,iMid },iMid - 1
				while value == fcompval( t[num] ) do
					tfound[1],num = num,num - 1
				end
				num = iMid + 1
				while value == fcompval( t[num] ) do
					tfound[2],num = num,num + 1
				end
				return tfound
			-- keep searching
			elseif fcomp( value,value2 ) then
				iEnd = iMid - 1
			else
				iStart = iMid + 1
			end
		end
	end
	function bintailset(t,value,fcompval,reversed)
		-- Initialise functions
		local fcompval = fcompval or default_fcompval
		local fcomp = reversed and fcompr or fcompf
		--	Initialise numbers
		local iStart,iEnd,iMid,iState = 1,#t,0,0
		-- Binary Search
		while iStart <= iEnd do
			-- calculate middle
			iMid = math.floor( (iStart+iEnd)/2 )
			-- get compare value
			local value2 = fcompval( t[iMid] )
			-- get all values that match
			if value == value2 then
				local tfound,num = iMid ,iMid - 1
				while value == fcompval( t[num] ) do
					tfound,num = num,num - 1
				end
				return tfound
			-- keep searching
			elseif fcomp( value,value2 ) then
				iEnd,iState = iMid - 1,0
			else
				iStart,iState = iMid + 1,1
			end
		end
		return iMid+iState
	end
end
--[[
	table.bininsert( table, value [, comp] )
	
	Inserts a given value through BinaryInsert into the table sorted by [, comp].
	
	If 'comp' is given, then it must be a function that receives
	two table elements, and returns true when the first is less
	than the second, e.g. comp = function(a, b) return a > b end,
	will give a sorted table, with the biggest value on position 1.
	[, comp] behaves as in table.sort(table, value [, comp])
	returns the index where 'value' was inserted
]]--
do
	-- Avoid heap allocs for performance
	local fcomp_default = function( a,b ) return a < b end
	function bininsert(t, value, fcomp)
		-- Initialise compare function
		local fcomp = fcomp or fcomp_default
		--	Initialise numbers
		local iStart,iEnd,iMid,iState = 1,#t,1,0
		-- Get insert position
		while iStart <= iEnd do
			-- calculate middle
			iMid = math.floor( (iStart+iEnd)/2 )
			-- compare
			if fcomp( value,t[iMid] ) then
				iEnd,iState = iMid - 1,0
			else
				iStart,iState = iMid + 1,1
			end
		end
		table.insert( t,(iMid+iState),value )
		return (iMid+iState)
	end
end


function kvarray()
   local reverse = {}
   local set = {}
   local q = {}
   setmetatable(set, { __index = {
       insert = function(set, value)
           if not reverse[value] then
               set[#set + 1] = value
               reverse[value] = #set
           end
       end,

       remove = function(set, value)
           local index = reverse[value]
           if index then
               reverse[value] = nil
               local top = set[#set]
               set[#set] = nil
               if top ~= value then
                   reverse[top] = index
                   set[index] = top
               end
           end
       end,

       push = function (set, key, itm)
               local qKey = q[key]
               if qKey == nil then
                       q[key] = {itm}
               else
                       qKey[#qKey + 1] = itm
               end
       end,

       pop = function (set, key)
         local t = q[key]
         if t ~= nil then
           local ret = table.remove (t, 1)
           if t[1] == nil then
             q[key] = nil
           end
           return ret
         end
       end
   }})
   return set
end